package com.woldier.algorithm.sort;

/**
 * description 选择排序
 * 从待排序范围内选出一个最大的元素放入最右端, 如下例子, 第一轮选出9 最大, 放入末尾
 * <pre>
 *       {@code
 *
 *
 * value 1 5 4 3 8 9
 * index 0 1 2 3 4 5
 *
 * 第一轮找出9最大, 那么将9对应索引的值与索引5处进行交换
 *                 |
 * value 1 5 4 3 8 9
 * index 0 1 2 3 4 5
 *
 * 第二轮找出8最大, 那么将8对应索引的值与索引4处值进行交换
 *               |
 * value 1 5 4 3 8 9
 * index 0 1 2 3 4 5
 *
 * 第三轮找出5最大, 那么将5对应索引的值与索引3处值进行交换
 *             |
 * value 1 3 4 5 8 9
 * index 0 1 2 3 4 5
 *       }
 *   </pre>
 *
 * @author: woldier wong
 * @date: 2023/12/27$ 16:09$
 */
public class SelectionSort {
    public static void selectionSort(int[] nums, int start, int end) {

        do {
            int maxIdx = start; //初始化最大值位置索引
            int maxNum = Integer.MIN_VALUE;  // 初始化最小值
            for (int i = start; i <= end; i++) {
                int num = nums[i]; //当前索引的值
                if (num > maxNum) { //如果当前值大于暂存的最大值, 并且记录索引位置
                    maxNum = num;
                    maxIdx = i;
                }
            }
            //经过for循环, 那么就找到了范围内最大值的位置, 此时就需要交换位置了
            nums[maxIdx] = nums[end];
            nums[end] = maxNum;
            end--;
        } while (end != start);
    }

    public static void selectionSort(int[] nums, int end){
        selectionSort(nums, 0, end);
    }
    public static void selectionSort(int[] nums) {
        selectionSort(nums, 0, nums.length - 1);
    }

    public static void main(String[] args) {
        int [] a = new int[]{1,5,4,3,8,9};
        selectionSort(a);
        for (int i : a) {
            System.out.print(i+",");
        }
    }
}
